package lec08ds02;

public class BinaryTree {
    String root;
    BinaryTree left;
    BinaryTree right;

    public BinaryTree(String root, BinaryTree left, BinaryTree right) {
        this.root = root;
        this.left = left;
        this.right = right;
    }

    public BinaryTree(String root) {
        this(root, null, null);
    }

    void preVisit() {
        System.out.print(root);
        if (left != null) left.preVisit();
        if (right != null) right.preVisit();
    }

    void postVisit() {

        if (left != null) left.postVisit();
        if (right != null) right.postVisit();
        System.out.print(root);
    }

    static BinaryTree createTree(String pre, String mid) {
        if (pre.length() == 0) return null;
        if (pre.length() == 1)
            return new BinaryTree(pre, null, null);


        String leftPre = "", leftMid = "";
        String rightPre = "", rightMid = "";
        int pos = mid.indexOf(pre.charAt(0));
        leftMid = mid.substring(0, pos);
        rightMid = mid.substring(pos + 1);
        for (char ch : pre.toCharArray()) {
            if (leftMid.indexOf(ch) >= 0)
                leftPre = leftPre + ch;
            if (rightMid.indexOf(ch) >= 0)
                rightPre = rightPre + ch;
        }
        BinaryTree left = createTree(leftPre, leftMid);
        BinaryTree right = createTree(rightPre, rightMid);

        return new BinaryTree(pre.charAt(0) + "", left, right);


    }

    public static void main(String[] args) {
//        BinaryTree a = new BinaryTree("a", null, null);
//        BinaryTree b = new BinaryTree("b", null, null);
//        BinaryTree c = new BinaryTree("c", null, null);
//        a.left = b;
//        a.right = c;
//        a.preVisit();
        BinaryTree tree = createTree("ABFCDGHEI", "BFAGDHCIE");
        tree.postVisit();
    }
}
